#include <cmath>
#include "sortingalgorithms.h"

//-------------------- PUBLIC METHODS ------------------------------------

// Sort items with BubbleSort algorithm (jump over specified fields number)
// from - starting index, to - ending index, jump - , desc - if true, use descending order
__device__ void bubbleSort(int * items, long from, long to, bool desc = false, long jump = 1){
    to++;

    if(from < 0){
        from += jump;
    }

//    cout << from << ", " << to << ", " << jump << endl;
    for(long ii=from;ii<to;ii+=jump){
        long jj;
        int temp;

        for(jj=from+jump;jj<to-(ii-from);jj++){
            if((items[jj-jump]>items[jj]) != desc){ //swap
                temp=items[jj-jump];

                items[jj-jump]=items[jj];
                items[jj]=temp;
            }
        }
    }
}

__global__ void horizontalPhase(int * items, long offset, long colsCnt){
    long jj =  blockIdx.x * blockDim.x + threadIdx.x;
    long start = colsCnt - offset + colsCnt*(jj-1);
    bool desc = ((jj+1)%2 == 0);
//                cout << start << ", " << start + colsCnt - 1 << endl;
    if(jj!=0)
        bubbleSort(items, start, start + colsCnt - 1, desc);
    else
        bubbleSort(items, 0, colsCnt-offset - 1);
//            cout << start << ", " << start + colsCnt - 1 << endl;
}

__global__ void verticalPhase(int * items, long offset, long itemsCnt, long colsCnt){
    long jj =  blockIdx.x * blockDim.x + threadIdx.x;
//    cout << jj-offset << ", " << itemsCnt-1 << endl;
    bubbleSort(items, jj-offset, itemsCnt-1, false, colsCnt);
//    cout << jj-offset << ", " << itemsCnt-1 << endl;
}

// Sort items with ShearSort algorithm
// For vertical and horizontal phases use BubbleSort algorithm
extern "C" void shearSort(int * items, unsigned long cnt, unsigned int blockCnt){
    long itemsCnt = long(cnt), rowsCnt = sqrt(itemsCnt), colsCnt = itemsCnt / rowsCnt;

    if(rowsCnt * colsCnt != itemsCnt) colsCnt++;

    long threadRowsCnt = ceil((double)rowsCnt / (double)blockCnt);
    long threadColsCnt = ceil((double)colsCnt / (double)blockCnt);

    long offset = rowsCnt * colsCnt - itemsCnt;
//    cout << rowsCnt << ", " << colsCnt << ", " << offset << endl;

    for(long ii=0;ii<log2(double(rowsCnt));ii++){
        // Horizontal phase - first row can be incomplete
//        for(long jj=0;jj<rowsCnt;jj++){
        horizontalPhase<<<blockCnt, threadRowsCnt>>>(items, offset, colsCnt);

        // Vertical phase
//        for(long jj=0;jj<colsCnt;jj++){
        verticalPhase<<<blockCnt, threadColsCnt>>>(items, offset, itemsCnt, colsCnt);
    }

//    for(long jj=0;jj<rowsCnt;jj++){
    horizontalPhase<<<blockCnt, threadRowsCnt>>>(items, offset, colsCnt);
}
